|
In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. ==Oriented graphs== A directed graph is called an oriented graph if it is the orientation of an undirected graph. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of and may be arrows of the graph).〔.〕 A tournament is an orientation of a complete graph. A polytree is an orientation of an undirected tree.〔.〕 Sumner's conjecture states that every tournament with 2''n'' − 2 vertices contains every polytree with ''n'' vertices.〔(Sumner's Universal Tournament Conjecture ), Douglas B. West, retrieved 2012-08-02.〕 The number of non-isomorphic oriented graphs with ''n'' vertices (for ''n'' = 1, 2, 3, …) is : 1; 2; 7; 42; 582; 21,480; 2,142,288; 575,016,219; 415,939,243,032; … . Oriented graphs are in one-to-one correspondence with complete directed graphs (graphs in which there is a directed edge in one or both directions between every pair of distinct vertices). A complete directed graph can be converted to an oriented graph by removing every 2-cycle, and conversely an oriented graph can be converted to a complete directed graph by adding a 2-cycle between every pair of vertices that are not endpoints of an edge; these correspondences are bijective. Therefore, the same sequence of numbers also solves the graph enumeration problem for complete digraphs. There is an explicit but complicated formula for the numbers in this sequence.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Orientation (graph theory)」の詳細全文を読む スポンサード リンク
|